package com.my.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class LinkedListProblems {


    public static void main(String[] args) {


        LinkedListProblems problems = new LinkedListProblems();

        ListNode node = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);
        ListNode node6 = new ListNode(6);
        ListNode node7 = new ListNode(7);
        node.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node6;
        node6.next = node7;

        System.out.println("node=====" + node);
        //System.out.println(problems.deleteDuplicates(node));
        System.out.println(problems.removeKNode(node, 3));
    }



    /**
     * @author zlx
     * @Description 删除链表的第k个节点
     * @Date 4/14/21
     * @Param [head, k]
     * @return com.my.leetcode.ListNode
     **/
    public ListNode removeKNode(ListNode head, int k){

        if(head == null || k <= 0){
            return head;
        }

        ListNode dumpy = new ListNode(0);
        dumpy.next = head;
        ListNode s = dumpy;
        ListNode q = s;
        for(int i = 0;i < k;i++){
            q = q.next;
            if(q == null){
                return head;
            }
        }

        while (q.next != null){
            s = s.next;
            q = q.next;
        }
        System.out.println("s=====" + s);
        s.next = s.next.next;
        return dumpy.next;
    }


    /**
     * @author zlx
     * @Description
     * @Date 3/25/21
     * @Param [head]
     * @return com.my.leetcode.ListNode
     **/
    public ListNode deleteDuplicates(ListNode head) {

        if(head == null || head.next == null){
            return head;
        }
        ListNode dumpy = new ListNode(0);
        dumpy.next = head;
        ListNode prev = dumpy;
        ListNode cur = prev.next;

        while (cur != null){

            ListNode next = cur.next;
            if(next == null){
                break;
            }
            if(cur.val != next.val){
                prev = cur;
                cur = cur.next;
                continue;
            }

            while (next != null && cur.val == next.val){
                cur = next;
                next = cur.next;
            }
            prev.next = next;
            cur = next;
        }
        return dumpy.next;

    }


    public ListNode reverseBetweenA(ListNode head, int left, int right) {

        if(left == right){
            return head;
        }
        ListNode dumpyNode = new ListNode(0);
        dumpyNode.next = head;
        ListNode prev = dumpyNode;
        ListNode p = prev.next;

        for(int i = 1;i < left;i++){
            prev = p;
            p = p.next;
        }

        for(int i = 1;i <= (right - left);i++){
            ListNode next = p.next;
            p.next = next.next;
            next.next = prev.next;
            prev.next = next;
        }

        return dumpyNode.next;
    }

    /**
     * @author zlx
     * @Description 61. 旋转链表 middle
     * 给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。
     *
     * 示例 1:
     *
     * 输入: 1->2->3->4->5->NULL, k = 2
     * 输出: 4->5->1->2->3->NULL
     * 解释:
     * 向右旋转 1 步: 5->1->2->3->4->NULL
     * 向右旋转 2 步: 4->5->1->2->3->NULL
     * 示例 2:
     *
     * 输入: 0->1->2->NULL, k = 4
     * 输出: 2->0->1->NULL
     * 解释:
     * 向右旋转 1 步: 2->0->1->NULL
     * 向右旋转 2 步: 1->2->0->NULL
     * 向右旋转 3 步: 0->1->2->NULL
     * 向右旋转 4 步: 2->0->1->NULL
     * @Date 2020-12-29
     * @Param [head, k]
     *
     * 解题思路： （1）计算链表长度len；（2）rotateTimes = k%len 计算实际移动的位置； (3) len - rotateTimes 后面的链表放到head的前面
     *
     * @return com.my.leetcode.ListNode
     **/
    public ListNode rotateRight(ListNode head, int k) {

        if(k == 0 || head == null || head.next == null){
            return head;
        }
        ListNode node = head;
        int len = 0;
        //计算链表长度
        while (node != null){
            len ++;
            node = node.next;
        }
        int rotateTimes = k % len;
        //不需要转
        if(rotateTimes == 0){
            return head;
        }
        int moveIndex = len - rotateTimes;
        //旋转后要放到前面的头节点
        ListNode prev = head;
        //旋转后的尾巴节点
        ListNode tail = head;
        for(int i = 0;i < moveIndex;i++){
            tail = prev;
            prev = prev.next;
        }
        tail.next = null;
        //查找旋转后要放到前面的节点的最后一个节点
        ListNode middle = prev;
        while (middle.next != null){
            middle = middle.next;
        }
        middle.next = head;
        return prev;
    }

    /**
     * @author zlx
     * @Description 147. 对链表进行插入排序 middle
     * 对链表进行插入排序。
     *
     *
     * 插入排序的动画演示如上。从第一个元素开始，该链表可以被认为已经部分排序（用黑色表示）。
     * 每次迭代时，从输入数据中移除一个元素（用红色表示），并原地将其插入到已排好序的链表中。
     *
     *
     *
     * 插入排序算法：
     *
     * 插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
     * 每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
     * 重复直到所有输入数据插入完为止。
     *
     *
     * 示例 1：
     *
     * 输入: 4->2->1->3
     * 输出: 1->2->3->4
     * 示例 2：
     *
     * 输入: -1->5->3->4->0
     * 输出: -1->0->3->4->5
     * @Date 2020-11-20
     * @Param [head]
     * @return com.my.leetcode.ListNode
     **/
    public ListNode insertionSortList(ListNode head) {


        if(head == null || head.next == null){
            return head;
        }

        ListNode sortList = new ListNode(head.val);
        ListNode wait = head.next;

        while (wait != null){
            ListNode prev = null;
            ListNode cur = sortList;
            ListNode tmp = new ListNode(wait.val);
            boolean flag = false;
            while (cur != null){
                if(tmp.val <= cur.val){
                    flag = true;
                    if(prev != null) {
                        prev.next = tmp;
                        tmp.next = cur;
                    }else{
                        tmp.next = sortList;
                        sortList = tmp;
                    }
                    break;
                }else{
                    prev = cur;
                    cur = cur.next;
                }
            }

            if(!flag){
                if(tmp.val >= prev.val){
                    prev.next = tmp;
                    tmp.next = cur;
                }else{
                    tmp.next = sortList;
                    sortList = tmp;
                }
            }
            wait = wait.next;
        }

        return sortList;
    }


    public ListNode addTwoNumbersII(ListNode l1, ListNode l2) {

        ListNode res = new ListNode(0);
        ListNode node = res;
        int flag = 0;
        while (l1 != null && l2 != null){
            int val = l1.val + l2.val + flag;
            node.next = new ListNode(val%10);
            node = node.next;
            flag = val / 10;
            l1 = l1.next;
            l2 = l2.next;
        }

        ListNode tmp = l1 == null ? l2 : l1;
        while (tmp != null){
            int val = tmp.val + flag;
            node.next = new ListNode(val%10);
            node = node.next;
            flag = val / 10;
            tmp = tmp.next;
        }

        if(flag != 0){
            node.next = new ListNode(flag);
        }
        return res.next;
    }


    /**
     * @author zlx
     * @Description 328. 奇偶链表 middle
     * 给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。
     *
     * 请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。
     *
     * 示例 1:
     *
     * 输入: 1->2->3->4->5->NULL
     * 输出: 1->3->5->2->4->NULL
     * 示例 2:
     *
     * 输入: 2->1->3->5->6->4->7->NULL 
     * 输出: 2->3->6->7->1->5->4->NULL
     * 说明:
     *
     * 应当保持奇数节点和偶数节点的相对顺序。
     * 链表的第一个节点视为奇数节点，第二个节点视为偶数节点，以此类推。
     * @Date 2020-11-13
     * @Param [head]
     * @return com.my.leetcode.ListNode
     **/
    public ListNode oddEvenList(ListNode head) {

        if(head == null || head.next == null || head.next.next == null){
            return head;
        }
        ListNode odd = new ListNode(0);
        ListNode oddL = head;
        ListNode tailO = odd;
        ListNode even = new ListNode(0);
        ListNode evenL = head.next;
        ListNode tailE = even;

        while (oddL != null){
            tailO.next = new ListNode(oddL.val);
            tailO = tailO.next;
            if(oddL.next != null) {
                oddL = oddL.next.next;
            }else{
                break;
            }
        }


        while (evenL != null){
            tailE.next = new ListNode(evenL.val);
            tailE = tailE.next;
            if(evenL.next != null) {
                evenL = evenL.next.next;
            }else{
                break;
            }
        }

        System.out.println("odd:  " + odd);
        System.out.println("even:  " + even);

        tailO.next = even.next;
        return odd.next;
    }



    public void reorderListII(ListNode head) {
        if(head==null || head.next==null || head.next.next==null)return;

        // 1. 找中点，让slow指向中点，或左中点位置
        ListNode slow = head, fast = head.next;
        while (fast!=null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        // 2. 断开中点，反转后半部分
        ListNode head2 = null, next = slow.next;
        slow.next = null;
        slow = next;
        while(slow != null) {
            next = slow.next;
            slow.next = head2;
            head2 = slow;
            slow = next;
        }

        // 3. 合并链表head和head2
        ListNode curr = head;
        ListNode curr2 = head2;
        System.out.println("head===" + curr);
        System.out.println(curr2);
        while(curr != null && curr2!=null) {
            next = curr.next;
            curr.next = curr2;
            curr2 = curr2.next;
            curr.next.next = next;
            curr = next;
        }
    }

    /**
     * @author zlx
     * @Description 143. 重排链表 middle
     * 给定一个单链表 L：L0→L1→…→Ln-1→Ln ，
     * 将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…
     *
     * 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
     *
     * 示例 1:
     *
     * 给定链表 1->2->3->4, 重新排列为 1->4->2->3.
     * 示例 2:
     *
     * 给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.
     * @Date 2020-10-20
     * @Param [head]
     * @return void
     **/
    public void reorderList(ListNode head) {

        if(head == null || head.next == null){
            return ;
        }

        ListNode s = head, f = head.next;
        while (f != null && f.next != null){
            s = s.next;
            f = f.next.next;
        }

        ListNode reverseHalf = reverseNode(s.next);
        ListNode p = head;
        System.out.println(head);
        while (p != null && reverseHalf != null){
            System.out.println("reverseHafl======" + reverseHalf);
            ListNode next = p.next;
            p.next = reverseHalf;
            reverseHalf = reverseHalf.next;
            p.next.next = next;
            p = next;
        }

    }


    public ListNode reverseNode(ListNode node){

       ListNode head = new ListNode(0);
       while (node != null){
           ListNode pre = head.next;
           head.next = new ListNode(node.val);
           head.next.next = pre;
           node = node.next;
       }


       return head.next;
    }

    public void reorderListI(ListNode head) {

        if(head == null || head.next == null){
            return ;
        }

        List<ListNode> res = new ArrayList<>();
        ListNode node = head;
        while (node != null){
            res.add(node);
            node = node.next;
        }

        int i = 0, j = res.size() - 1;
        while (i < j){
            res.get(i).next = res.get(j);
            i++;
            if(i == j){
                break;
            }
            res.get(j).next = res.get(i);
            j--;
        }
        res.get(i).next = null;

    }


    /**
     * @author zlx
     * @Description 24. 两两交换链表中的节点 middle
     * 给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
     *
     * 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
     *
     *
     *
     * 示例:
     *
     * 给定 1->2->3->4, 你应该返回 2->1->4->3.
     * @Date 2020-10-13
     * @Param [head]
     * @return com.my.leetcode.ListNode
     **/
    public ListNode swapPairs(ListNode head) {

        if(head == null || head.next == null){
            return head;
        }

        ListNode slow = head;
        ListNode quick = head.next;

        ListNode pre = new ListNode(0);
        ListNode headR = pre;
        pre.next = head;
        while (quick != null){
            slow.next = quick.next;
            quick.next = slow;
            pre.next = quick;
            pre = slow;
            slow = slow.next;
            if(slow == null){
                break;
            }
            quick = slow.next;
        }
        return headR.next;
    }


    /**
     * @author zlx
     * @desc 25. K 个一组翻转链表 hard
     * 给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
     *
     * k 是一个正整数，它的值小于或等于链表的长度。
     *
     * 如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
     *
     *
     *
     * 示例：
     *
     * 给你这个链表：1->2->3->4->5
     *
     * 当 k = 2 时，应当返回: 2->1->4->3->5
     *
     * 当 k = 3 时，应当返回: 3->2->1->4->5
     *
     *
     *
     * 说明：
     *
     * 你的算法只能使用常数的额外空间。
     * 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交
     * @date  2020-05-28
     * @param head
     * @param k
     * @return com.my.leetcode.ListNode
     **/
    public ListNode reverseKGroup(ListNode head, int k) {

        if(head == null || k == 0){
            return head;
        }
        ListNode myHead = new ListNode(0);
        myHead.next = head;

        ListNode tail = head;
        ListNode reverseNode;
        ListNode prev = myHead;
        int count = 1;
        int len = lengthOfLinkedList(head);
        int times = len / k;
        for(int i = 0;i < times;i++){
            while (tail != null && tail.next != null){
                if(count == k){
                    count = 1;
                    break;
                }else {
                    reverseNode = tail.next;
                    tail.next = reverseNode.next;
                    reverseNode.next = prev.next;
                    prev.next = reverseNode;
                    count++;
                }
            }
            prev = tail;
            tail = tail.next;
        }
        return myHead.next;
    }

    public int lengthOfLinkedList(ListNode head){
        if(head == null){
            return 0;
        }
        ListNode tmp = head;
        int count = 0;
        while(tmp != null){
            tmp = tmp.next;
            count++;
        }
        return count;
    }


    //反转链表
    public ListNode reverseList(ListNode head){

        if(head == null || head.next == null){
            return head;
        }
        ListNode tail = head;
        ListNode next ;
        ListNode pre = head;
        while (tail.next != null){

            next = pre.next;
            tail.next = next.next;
            next.next = pre;
            pre = next;
        }
        return pre;
    }


    /**
     * @author zlx
     * @desc 23. 合并K个排序链表
     * hard
     * 合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。
     *
     * 示例:
     *
     * 输入:
     * [
     *   1->4->5,
     *   1->3->4,
     *   2->6
     * ]
     * 输出: 1->1->2->3->4->4->5->6
     * @date 20:42 2020-04-27
     * @param lists
     * @return com.my.leetcode.ListNode
     *
     *
     * 解题思路：基于分而治之的思想，两两合并后再合并， 时间复杂度是：O(KNlogN), 空间复杂度：O(logK)
     **/
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists == null || lists.length <= 0){
            return null;
        }
        return mergeList(lists, 0, lists.length - 1);
    }

    public ListNode mergeList(ListNode[] lists, int l, int r){

        if(l == r){
            return lists[r];
        }else if (l > r){
            return null;
        }
        int middle = (l + r) / 2;
        return mergeTwoList(mergeList(lists, l, middle), mergeList(lists, middle + 1, r));
    }

    public ListNode mergeTwoList(ListNode a, ListNode b){

        if(a == null || b == null){
            return a == null ? b : a;
        }
        ListNode head = new ListNode(0);
        ListNode last = head;
        while (a != null || b != null){
            if(a == null){
                System.out.println("----------a null------" + b);
                last.next = b;
                break;
            }else if(b == null){
                last.next = a;
                break;
            }
            if(a.val < b.val){
                last.next = new ListNode(a.val);
                a = a.next;
            }else if(a.val > b.val){
                last.next = new ListNode(b.val);
                b = b.next;
            }else{
                last.next = new ListNode(a.val);
                last = last.next;
                last.next = new ListNode(b.val);
                a = a.next;
                b = b.next;
            }
            last = last.next;
        }
        return head.next;

    }

    /**
     * 876. 链表的中间结点
     * 2020/03/23  easy
     * 给定一个带有头结点 head 的非空单链表，返回链表的中间结点。
     *
     * 如果有两个中间结点，则返回第二个中间结点。
     *
     *
     *
     * 示例 1：
     *
     * 输入：[1,2,3,4,5]
     * 输出：此列表中的结点 3 (序列化形式：[3,4,5])
     * 返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
     * 注意，我们返回了一个 ListNode 类型的对象 ans，这样：
     * ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.
     * 示例 2：
     *
     * 输入：[1,2,3,4,5,6]
     * 输出：此列表中的结点 4 (序列化形式：[4,5,6])
     * 由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。
     * @param head
     * @return
     */
    public ListNode middleNode(ListNode head) {

        if(head == null || head.next == null){
            return head;
        }

        ListNode slow = head;
        ListNode fast = slow.next;
        while (fast != null && fast.next != null){

            slow = slow.next;
            fast = fast.next.next;
        }

        if(fast != null){
            return slow.next;
        }
        return slow;
    }

    /**
     * 142. Linked List Cycle II
     *
     *
     * 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
     *
     * 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
     *
     * 说明：不允许修改给定的链表。
     *
     *  
     *
     * 示例 1：
     *
     * 输入：head = [3,2,0,-4], pos = 1
     * 输出：tail connects to node index 1
     * 解释：链表中有一个环，其尾部连接到第二个节点。
     *
     *
     * 示例 2：
     *
     * 输入：head = [1,2], pos = 0
     * 输出：tail connects to node index 0
     * 解释：链表中有一个环，其尾部连接到第一个节点。
     *
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/linked-list-cycle-ii
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     *
     */
    public ListNode detectCycle(ListNode head) {

        if(head == null || head.next == null){
            return null;
        }

        ListNode slow = head.next;
        ListNode fast = head.next.next;

        boolean isCycle = false;
        while (fast != null && fast.next != null){
            if(fast == slow){
                isCycle = true;
                break;
            }
            slow = slow.next;
            fast = fast.next.next;
        }

        if(!isCycle){
            return null;
        }

        ListNode tmp = head;

        while (tmp != slow){
            tmp = tmp.next;
            slow = slow.next;
        }

        return slow;
    }


    /**
     * 234. 回文链表
     * simple
     * 请判断一个链表是否为回文链表。
     *
     * 解法1：链表反转，对比
     * 解法2：使用快慢指针，前半部分反转，后取值对比
     *
     * 示例 1:
     *
     * 输入: 1->2
     * 输出: false
     * 示例 2:
     *
     * 输入: 1->2->2->1
     * 输出: true
     * @param head
     * @return
     */
    public static boolean isPalindrome(ListNode head) {

        if(head == null || head.next == null){
            return true;
        }

        //解法二
        ListNode fast = head;
        ListNode slow = head;
        ListNode prev = head;
        ListNode prevprev = null;
        while (fast != null && fast.next != null){

            prev = slow;
            slow = slow.next;
            fast = fast.next.next;

            prev.next = prevprev;
            prevprev = prev;
        }

        if(fast != null){

            slow = slow.next;
        }

        System.out.println(prev);
        while (prev != null && slow != null){

            if(prev.val != slow.val){
                return false;
            }
            prev = prev.next;
            slow = slow.next;
        }
        return true;




        //解法一
        /*ListNode reveseList = new ListNode(head.val);

        ListNode tmpList = head.next;
        while (tmpList != null){

            ListNode tmp = new ListNode(tmpList.val);
            tmp.next = reveseList;
            reveseList = tmp;
            tmpList = tmpList.next;
        }

        System.out.println(reveseList);

        while (head != null && reveseList != null){

            if(head.val != reveseList.val){
                return false;
            }
            head = head.next;
            reveseList = reveseList.next;
        }
        return true;*/
    }


    /**
     *
     * 92. 反转链表 II
     * 反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
     *
     * 说明:
     * 1 ≤ m ≤ n ≤ 链表长度。
     * @param head
     * @param m
     * @param n
     * @return
     */
    public static ListNode reverseBetween(ListNode head, int m, int n) {
        if(head == null || head.next == null){
            return head;
        }
        //添加一个固定的头部作为标示
        ListNode fixedHead = new ListNode(0);
        fixedHead.next = head;
        //交换后最后一个点
        ListNode last = fixedHead;
        //固定不变的交换起点
        ListNode pre = fixedHead;
        for(int i =1;i <= m;i++){
            last = last.next;
        }
        for(int i = 1; i < m;i++){
            pre = pre.next;
        }
        System.out.println("pre is :" + pre);
        System.out.println("last is: " + last);
        for(int i = m+1;i <= n;i++){

            ListNode tmp = last.next;
            last.next = tmp.next;
            tmp.next = pre.next;
            pre.next = tmp;
        }

        return fixedHead.next;

    }


    /**
     *
     * 2. 两数相加
     * 给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
     *
     * 如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
     * @param l1
     * @param l2
     * @return
     */
    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {

        if(l1 == null && l2 == null){
            return null;
        }
        if(l1 == null && l2 != null){
            return l2;
        }

        if(l1 != null && l2 == null){
            return l1;
        }

        int carry = 0;
        ListNode head = new ListNode(0);
        ListNode pt = head;
        while(l1 != null && l2 != null){
            int tmpVal = l1.val + l2.val + carry;
            carry = tmpVal / 10;
            tmpVal = tmpVal % 10;
            pt.next = new ListNode(tmpVal);
            pt = pt.next;
            l1 = l1.next;
            l2 = l2.next;
        }
        while(l1 != null){
            int tmpVal = l1.val + carry;
            carry = tmpVal / 10;
            tmpVal = tmpVal % 10;
            pt.next = new ListNode(tmpVal);
            pt = pt.next;
            l1 = l1.next;
        }

        while(l2 != null){
            int tmpVal = l2.val + carry;
            carry = tmpVal / 10;
            tmpVal = tmpVal % 10;
            pt.next = new ListNode(tmpVal);
            pt = pt.next;
            l2 = l2.next;
        }

        if(l1 == null && l2 == null && carry != 0){
            pt.next = new ListNode(carry);
        }
        return head.next;


    }



    public static ListNode reverseListNodeII(ListNode node){

        if(node == null || node.next == null){
            return node;
        }
        ListNode head = new ListNode(0);
        head.next = node;
        ListNode tail = head.next;
        ListNode prev = head.next;
        while(tail.next != null){

            head.next = tail.next;
            tail.next = tail.next.next;
            head.next.next = prev;
            prev = head.next;

        }
        return head.next;
    }


    /**
     * 206. 反转链表
     * @param node
     * @return
     */
    public static ListNode reverseListNode(ListNode node){

        if(node == null || node.next == null){
            return node;
        }
        ListNode head = new ListNode(0);
        while(node != null){

            ListNode tmp = new ListNode(node.val);
            tmp.next = head.next;
            head.next = tmp;
            node = node.next;
        }
        return head.next;
    }

    /**
     * 求链表长度
     * @param node
     * @return
     */
    public static int listNodeLength(ListNode node){

        if(node == null){
            return 0;
        }

        int res = 0;
        while (node != null){
            res ++;
            node = node.next;
        }
        return res;
    }


    /**
     * @author zlx
     * @Description 160. 相交链表
     * 编写一个程序，找到两个单链表相交的起始节点。
     *
     * @Date 4/8/21
     * @Param [headA, headB]
     * @return com.my.leetcode.ListNode
     **/
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {

        ListNode a = headA;
        ListNode b = headB;
        while(a != b){
            a = a != null ? a.next : headB;
            b = b != null ? b.next : headA;
        }
        return a;
    }
}
